'''
@Author: shj
@Date: 2020-06-02 12:23:21
@LastEditTime: 2020-06-02 19:39:45
@LastEditors: shj
@Description:  合并两个排序的链表
@FilePath: /python3/algorithms/offer_code/16_merge_tow_sorted_linked_list.py
'''
'''
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路
法1：迭代
初始化：定义cur指向新链表的头结点
操作：
    如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值
    否则，让l2指向下一个结点值
    循环步骤1,2，直到l1或者l2为nullptr
    将l1或者l2剩下的部分链接到cur的后面 

法2 递归
    递归出口：
    当某链表为空时，返回另一链表
    递归内容：
    从两个链表中分别取一节点，二者较小的做新链表节点，然后小节点所在的链表后移一位

'''


# 前置可能用到的条件（针对法1）
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # 法1
        # 初始化头节点，当前节点
        newHead = cur = ListNode(None)
        # 两个链表未出现取尽
        while pHead1 and pHead2:
            # cur指向节点值小的节点
            if pHead1.val < pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            # 更新插入节点后的新链表的当前节点位置
            cur = cur.next
        # 将未取尽链表链接到新链表末端
        # cur.next = pHead1 if pHead2 is None else pHead2 # 等价
        cur.next = pHead1 or pHead2
        return newHead.next
        '''法2
        # 未出现取尽的链表
        if pHead1 and pHead2:
            # 取节点值小的节点做新链表的节点
            (pHead1,
             pHead2) = (pHead2,
                        pHead1) if pHead2.val < pHead1.val else (pHead1,
                                                                 pHead2)
            # 递归
            pHead1.next = self.Merge(pHead1.next, pHead2)
        # 返回新节点
        # python return None or not(None),优先返回not(None)
        return pHead1 or pHead2
        '''